﻿using magic8ballUtility;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;

namespace magic8ballUtility.Test.Regex
{
    
    
    /// <summary>
    ///This is a test class for RegexToNFATest and is intended
    ///to contain all RegexToNFATest Unit Tests
    ///</summary>
    [TestClass()]
    public class RegexToNFATest
    {


        private TestContext testContextInstance;

        /// <summary>
        ///Gets or sets the test context which provides
        ///information about and functionality for the current test run.
        ///</summary>
        public TestContext TestContext
        {
            get
            {
                return testContextInstance;
            }
            set
            {
                testContextInstance = value;
            }
        }

        #region Additional test attributes
        // 
        //You can use the following additional attributes as you write your tests:
        //
        //Use ClassInitialize to run code before running the first test in the class
        //[ClassInitialize()]
        //public static void MyClassInitialize(TestContext testContext)
        //{
        //}
        //
        //Use ClassCleanup to run code after all tests in a class have run
        //[ClassCleanup()]
        //public static void MyClassCleanup()
        //{
        //}
        //
        //Use TestInitialize to run code before running each test
        //[TestInitialize()]
        //public void MyTestInitialize()
        //{
        //}
        //
        //Use TestCleanup to run code after each test has run
        //[TestCleanup()]
        //public void MyTestCleanup()
        //{
        //}
        //
        #endregion


        /// <summary>
        /// Prihvaća znak
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaZnak()
        {
            RegexToNFA target = new RegexToNFA("a");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "a"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "b"));

            target = new RegexToNFA("t");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "t"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "x"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"\t"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "\t"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "a"));


            target = new RegexToNFA(@"\_");
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "_"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), " "));

            target = new RegexToNFA(@"_");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "_"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), " "));

            target = new RegexToNFA(@" ");
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "_"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), " "));

            target = new RegexToNFA(@"\}");
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "\\}"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "}"));

            target = new RegexToNFA(@"'");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "'"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "\'"));

            target = new RegexToNFA(@"\'");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "'"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "\'"));
        }

        /// <summary>
        /// Prihvaća niz nadovezanih znakova
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaNizZnakova()
        {
            RegexToNFA target = new RegexToNFA("aabbd");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "aabbd"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "aaabbd"));
        }

        /// <summary>
        /// Prihvaća niz nadovezanih znakova sa prefiksiranim znakovima
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaNizSaPrefiksiranimZnakovima()
        {
            RegexToNFA target = new RegexToNFA(@"aab\\bd");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aab\bd"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "aaabbd"));
            
            target = new RegexToNFA(@"aab\_bd");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aab bd"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "aaabbd"));
        }

        /// <summary>
        /// Prihvaća Kleenov operator
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaKleenovOperator()
        {
            RegexToNFA target = new RegexToNFA(@"aab\|b*d");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aab|bbbd"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aab|d"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"aab|"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"aab|dbbbd"));

            target = new RegexToNFA(@"c(a)*b");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"cab"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"cb"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"caaab"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"ca"));
            
        }

        /// <summary>
        /// Prihvaća uniju
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaUniju()
        {
            RegexToNFA target = new RegexToNFA(@"aab|b*");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aab"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"bbb"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @""));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"aaab"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"aabb"));

            target = new RegexToNFA(@"a|$|b");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"a"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"b"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @""));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"aa"));

            target = new RegexToNFA(@"a(c|v)a");
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"ca"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"ba"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aca"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"ava"));
        }

        /// <summary>
        /// Prihvaća ugnježđenu uniju
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaUgnjezdjenuUniju()
        {
            RegexToNFA target = new RegexToNFA(@"aab|(a|b)*");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aab"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"bbb"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @""));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aaaaa"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"aaabc"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aabb"));

            target = new RegexToNFA(@"a|$|b");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"a"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"b"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @""));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"aa"));
        }

        /// <summary>
        /// Prihvaća zagrade
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaZagrade()
        {
            RegexToNFA target = new RegexToNFA(@"(a)|(a*b)a|(b)");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"a"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"b"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @""));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"abaa"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"ba"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aba"));
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), @"aaba"));

            target = new RegexToNFA(@"a|(b*)");
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"ab"));

        }      

        /// <summary>
        /// Prihvaća \n
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaNoviRed()
        {
            RegexToNFA target = new RegexToNFA("\n");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "\n"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"\n"));
           
        }

        /// <summary>
        /// Prihvaća \t
        /// </summary>
        [TestMethod()]
        public void RegexPrihvacaTabulator()
        {
            RegexToNFA target = new RegexToNFA("\t");
            Assert.AreEqual(true, SimulirajNFA(target.DohvatiAutomat(), "\t"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), @"\t"));
            Assert.AreEqual(false, SimulirajNFA(target.DohvatiAutomat(), "t"));

        }

        /// <summary>
        /// Simulira rad nedeterminističkog konačnog automata sa epsilon prijelazima
        /// </summary>
        /// <param name="listaStanja">lista stanja automata</param>
        /// <param name="str">ulazni niz</param>
        /// <returns>true ako se niz prihvaća ili false ako ne</returns>
        private bool SimulirajNFA(List<RegexToNFA.Stanje> listaStanja, string str)
        {
            HashSet<int> trenutnaStanja = new HashSet<int>();
            trenutnaStanja.Add(0);
 
            // simulira se rad automata znak po znak niza
            for (int i = 0; i < str.Length; i++)
            {
                trenutnaStanja = KorakSimulacije(listaStanja, trenutnaStanja, str[i]);
            }

            // dohvaćaju se sva stanja u koja se može doći epislon prijelazima
            while (true)
            {
                int staraVelicinaSkupaPrijelaza = trenutnaStanja.Count;
                trenutnaStanja.UnionWith(DodajEPrijelaze(listaStanja, trenutnaStanja));
                if (staraVelicinaSkupaPrijelaza - trenutnaStanja.Count == 0)
                    break;
            }

            // traži se prihvatljivo stanje u svim završnim stanjima automata
            // i svim stanjima do kojih se iz njih može doći epsilon prijelazima
            bool match = false;
            foreach (var indeksStanja in trenutnaStanja)
            {
                if (listaStanja.Find(x => x.Id == indeksStanja).Prihvatljivo)
                    match = true;
            }

            return match;
        }

        /// <summary>
        /// Odrađuje korak simulacije
        /// </summary>
        /// <param name="listaStanja">lista stanja eNKA</param>
        /// <param name="trenutnaStanja">skup trenutnih stanja eNKA</param>
        /// <param name="c">ulazni znak</param>
        /// <returns>skup stanja nakon konzumacije znaka c</returns>
        private HashSet<int> KorakSimulacije(List<RegexToNFA.Stanje> listaStanja, HashSet<int> trenutnaStanja, char c)
        {
            HashSet<int> novaStanja = new HashSet<int>();
            
            // dohvaća sve prijelaze za znak
            foreach (var indeksStanja in trenutnaStanja)
            {
                novaStanja.UnionWith(listaStanja.Find(x => x.Id == indeksStanja).DohvatiPrijelaze(c));
            }

            ISet<int> epsilonPrijelazi = DodajEPrijelaze(listaStanja, trenutnaStanja);
            // dohvaća sva stanja do kojih se može doći epsilon prijelazima
            while (true)
            {
                int staraVelicinaSkupaPrijelaza = epsilonPrijelazi.Count;
                epsilonPrijelazi.UnionWith(DodajEPrijelaze(listaStanja, epsilonPrijelazi));
                if (staraVelicinaSkupaPrijelaza - epsilonPrijelazi.Count == 0)
                    break;
            }

            // dodaje stanja do kojih se može doći prijelazom za znak c iz stanja do
            // kojih se došlo epsilon produkcijama
            foreach (var indeksStanja in epsilonPrijelazi)
            {
                novaStanja.UnionWith(listaStanja.Find(x => x.Id == indeksStanja).DohvatiPrijelaze(c));
            }
            return novaStanja;
       
        }

        /// <summary>
        /// Dohvaća stanja do kojih se može doći epsilon produkcijama iz skupa
        /// trenutnih stanja
        /// </summary>
        /// <param name="listaStanja">lista stanja automata</param>
        /// <param name="trenutnaStanja">trenutna stanja automata</param>
        /// <returns>stanja do kojih se došlo epsilon prijelazima</returns>
        private ISet<int> DodajEPrijelaze(List<RegexToNFA.Stanje> listaStanja, ISet<int> trenutnaStanja)
        {
            HashSet<int> ePrijelazi = new HashSet<int>();
           
            foreach (var indeksStanja in trenutnaStanja)
            {
                ePrijelazi.UnionWith(listaStanja.Find(x => x.Id == indeksStanja).DohvatiPrijelaze('€'));
            }
            
            return ePrijelazi;
        }
    }
}
